package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class FindTheDuplicateNumber {

  public static void main(String[] args) {
    Solution solution = new FindTheDuplicateNumber().new Solution();
    // put your test code here
    // solution.findDuplicate(new int[]{1, 3, 4, 2, 3});
  }
  // leetcode submit region end(Prohibit modification and deletion)

  // leetcode submit region begin(Prohibit modification and deletion)
  class Solution {
    public int findDuplicate(int[] nums) {
      if (nums == null || nums.length < 1) {
        return -1;
      }

      int slow = 0;

      int fast = 0;

      // 让快慢指针相遇
      while (true) {

        // 慢指针走一步
        // 快指针走两步
        slow = nums[slow];
        fast = nums[nums[fast]];

        // 相遇
        if (slow == fast) {
          break;
        }
      }

      // 快指针归零，慢指针继续走， 快指针改为走1步
      fast = 0;
      while (true) {
        slow = nums[slow];
        fast = nums[fast];
        if (slow == fast) {
          return slow;
        }
      }

    }
  }
}
